package com.jiang.专题.滑动窗口.Q76;

import java.util.Arrays;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/22 15:25
 */
class Solution {
    public String minWindow(String s, String t) {
        int[] dp = new int[58];
        for (int i = 0; i < t.length(); i++) {
            dp[t.charAt(i) - 'A']--;
        }
        int cnt = (int) Arrays.stream(dp).filter(n -> n < 0).count();
        int len = Integer.MAX_VALUE;
        int startIndex = -1;
        int l = 0, r = 0;
        while (r < s.length()) {
            if (++dp[s.charAt(r) - 'A'] == 0) {
                cnt--;
            }

            while(cnt == 0) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    startIndex = l;
                }
                if(--dp[s.charAt(l) - 'A'] < 0) {
                    cnt++;
                }
                l++;
            }
            r++;
        }
        return startIndex == -1 ? "" : s.substring(startIndex, startIndex + len);
    }
}
